'''
@author: Kevin Zhao
@data:Dec 02,2012 
@note:
Matrix multiplication

@todo: 
(1)use index calculation 重写 matrix multiplication

def simple_dc(A_index,B_index,C_index)
example:A_index{row-start,row-end,col-start,col-end}
直到n=1这一步为止，都不做实际计算，只做index calculation
'''
    
'''create new matrix filled with all zeros as its content'''
def create_new_matrix(m, n):
    # Create empty matrix filled with all zeros
    new_matrix = [[0 for row in range(n)] for col in range(m)]
    return new_matrix
def create_sub_matrix(matrix, sub_matrix_index):
    row_start = sub_matrix_index['row-start']
    row_end = sub_matrix_index['row-end']
    col_start = sub_matrix_index['col-start']
    col_end = sub_matrix_index['col-end']
    result = [[matrix[row][col] for row in range(row_start, row_end)] for col in range(col_start, col_end)]
    return result

'''print out the matrix content'''
def show(matrix):
    # Print out matrix
    for col in matrix:
        print col 
'''
Brute force matrix multiplication,which takes Theta(n^3)
'''    
def brute_force_mm(matrix1, matrix2):
    # Matrix multiplication
    if len(matrix1[0]) != len(matrix2):
        # Check matrix dimensions
        print 'Matrices must be m*n and n*p to multiply!'
    else:
        # Multiply if correct dimensions
        new_matrix = create_new_matrix(len(matrix1), len(matrix2[0]))
        for i in range(len(matrix1)):
            for j in range(len(matrix2[0])):
                for k in range(len(matrix2)):
                    new_matrix[i][j] += matrix1[i][k] * matrix2[k][j]
        return new_matrix




'''
Simple recursive divide-and-conquer algorithm for matrix multiplication

@param matrix_A & matrix_B: matrix to be multiplied
@param matrix_C:result  
'''
def simple_dc(matrix_A, matrix_B , matrix_C):
    n = len(matrix_A)
    #Base case
    if not (matrix_A and matrix_B):
        return 0
    
    m = len(matrix_B[0])
    
    if n == 1:
        return brute_force_mm(matrix_A,matrix_B)
    
    if n != m:
        # Check matrix dimensions
        print 'Matrices must be m*n and n*p to multiply!'
    
    if n % 2 != 0 or m % 2 != 0:
        # Check whether n is the exact power of 2
        print 'Matrix size n is not the exact power of 2'
    
    #Divide each matrix into two n/2 sub-matrixes 
    matrix_A11_index = {'row-start':0, 'row-end':n / 2, 'col-start':0, 'col-end':m / 2}
    matrix_A12_index = {'row-start':0, 'row-end':n / 2, 'col-start':m / 2, 'col-end':m}
    matrix_A21_index = {'row-start':(n / 2) + 1, 'row-end':n, 'col-start':0, 'col-end':m / 2}
    matrix_A22_index = {'row-start':(n / 2) + 1, 'row-end':n, 'col-start':(m / 2) + 1, 'col-end':m}

    matrix_B11_index = {'row-start':0, 'row-end':m / 2, 'col-start':0, 'col-end':n / 2}
    matrix_B12_index = {'row-start':0, 'row-end':m / 2, 'col-start':(n / 2) + 1, 'col-end':n}
    matrix_B21_index = {'row-start':m / 2, 'row-end':m, 'col-start':0, 'col-end':n / 2}
    matrix_B22_index = {'row-start':(m / 2) + 1, 'row-end':m, 'col-start':(n / 2) + 1, 'col-end':n}
    #Combine
    
    matrix_C[0][0] = simple_dc(create_sub_matrix(matrix_A, matrix_A11_index), create_sub_matrix(matrix_B, matrix_B11_index), matrix_C) + simple_dc(create_sub_matrix(matrix_A, matrix_A12_index), create_sub_matrix(matrix_B, matrix_B21_index), matrix_C)#C11
    matrix_C[0][1] = simple_dc(create_sub_matrix(matrix_A, matrix_A11_index), create_sub_matrix(matrix_B, matrix_B12_index), matrix_C) + simple_dc(create_sub_matrix(matrix_A, matrix_A12_index), create_sub_matrix(matrix_B, matrix_B22_index), matrix_C)#C12
    matrix_C[1][0] = simple_dc(create_sub_matrix(matrix_A, matrix_A21_index), create_sub_matrix(matrix_B, matrix_B11_index), matrix_C) + simple_dc(create_sub_matrix(matrix_A, matrix_A22_index), create_sub_matrix(matrix_B, matrix_B21_index), matrix_C)#C21
    matrix_C[1][1] = simple_dc(create_sub_matrix(matrix_A, matrix_A21_index), create_sub_matrix(matrix_B, matrix_B12_index), matrix_C) + simple_dc(create_sub_matrix(matrix_A, matrix_A22_index), create_sub_matrix(matrix_B, matrix_B22_index), matrix_C)#C22
    
    return matrix_C
'''
TEST
'''
a = [[2, 3, 4, 7], [3, 3, 8, 9]]         # 2x4 matrix
b = [[1, 3], [5, 4], [7, 8], [9, 2]]       # 4x2 matrix
c = brute_force_mm(a, b)

n = len(a)
m = len(b)
matrix_C = create_new_matrix(n, n)
show(simple_dc(a, b, matrix_C))
#show(c1) 

#matrix_A11_index = matrix_B11_index = {'row-start':0, 'row-end':n / 2, 'col-start':0, 'col-end':n / 2}
#    matrix_A12_index = matrix_B12_index = {'row-start':0, 'row-end':n / 2, 'col-start':(n / 2) + 1, 'col-end':n}
#    matrix_A21_index = matrix_B21_index = {'row-start':(n / 2) + 1, 'row-end':n, 'col-start':0, 'col-end':n / 2}
#    matrix_A22_index = matrix_B22_index = {'row-start':(n / 2) + 1, 'row-end':n, 'col-start':(n / 2) + 1, 'col-end':n}
#show(create_sub_matrix(a, matrix_A11_index))
#show(create_sub_matrix(a, matrix_A12_index))
#show(create_sub_matrix(a, matrix_A21_index))
#show(create_sub_matrix(a, matrix_A22_index))


